The interest in statistical testing has increased in recent years for two main reasons: the growing complexity and non-determinism of the environments in which modern software is expected to operate (the Internet being the most popular example) and the higher levels of reliability required for some applications. Indeed, reliability assessment is crucial for systems with safety and fault-tolerance requirements. Such demands are difficult to address with traditional testing techniques. The complexity of the software itself and its interface may require that a test engineer develop test cases from a complex model describing the application. The use of automated tools is inevitable as such applications are simply too complex to test using manual tests.
This poses further problems: how to create test scripts with hundreds or thousands of tests in an effective way and how to update such scripts efficiently when there is a change in the product.
A usage model characterises the operational use of a software system, where the software is used in a specific environment and the user may be a person, a hardware device, other software, or a group of users. A software use may be a working session, transaction or any service unit limited by start and finish events.
The model structure is composed of a state set and the transitions between the states, constituting a graph. The graph nodes represent the model states, and the graph arcs represent transitions between states. The structure describes the possible uses of the software. A probability distribution associated with the model describes the expected use of the software.
Statistical testing with usage models is mostly based in Markov chains. However, a Markov chain for a complex application can easily reach hundreds or thousands of states, making modelling and maintenance a difficult task. Moreover, in order to generate the test script, it is necessary to add implementation related information to the usage model.
Accounts of usage models based on Markov chains are given by Tramell [Trammell, C. “Quantifying the Reliability of Software: Statistical Testing Based on a Usage Model,” 208-218. Proceedings of the Second IEEE International Symposium on Software Engineering Standards. Montreal, Quebec, Canada, August 21-25, 1995.] and Kallepalli [C. Kallepalli and J. Tian, “Measuring and Modeling Usage and Reliability for Statistical Web Testing”, IEEE Trans. on Software Engineering, Vol. 27, No. 11, pp. 1023-1036, November, 2001.].
A simple Markov chain usage model is shown in FIG. 1. The system has four states, Start, Error Message, Menu and Termination. From the ‘Start’ state, a user enters a password. If the password is incorrect, the Error Message is displayed. This occurs with a probability of 0.2. From the Error Message, the system always reverts to Start. If the password is correct, the system proceeds to the Menu state. This occurs with a probability of 0.8. From the menu the user can only terminate the program.
The evolution of the system is represented by transitions from one state to another and these transitions are assumed to happen in an instantaneous way.
The probabilities of transition of Markov chains are often represented by matrices. A transition matrix for the system of FIG. 1 is shown in Table 1 below.
TABLE 1StartError MessageMenuTerminationStart00.20.80Error Message1000Menu0001Termination1000
In general, the time and memory worst-case complexity of test case generation with a Markov chain usage model is proportional to the size of the transition matrix used to represent the model, i.e. proportional to the square of the number of states. This number grows very fast with the number of states.
A SAN consists of a number of individual stochastic automata that operate in a somewhat independent way.1 Each automaton is represented by a certain number of states, along with rules or probability functions that rule the movements from one state of the automaton to another. The state of the automata network is determined by the states that each one of the constituent automata occupies at a time t. 1 A. G. Farina, F. M. Oliveira. Research Report no. 23, CPPGCC-PUCRS, Porto Alegre, Brazil, March 2002.
More formally, given a set S of states (local states), let A={A1, A2, . . . An} be a set of automata, wherein each automaton Ai is a subset of S. Then a SAN is a structure (G, E, Pe, Pt, I), where:
G={G1, G2, . . . Gm} is a set of global states, such that each Gi is an element of A1×A2× . . . ×An. In other words, each global state is a combination of local states of the automata.
E={E1, E2, Ek} is a set of events. Each event is a function Ei: G→P(G). In other words, each event maps global states into sets of global states. When the event is applied, the SAN can go to any element of the set specified by the function, depending on the probabilities assigned to the event. Since a global state is a list of local states, the function describes for each automaton in the network what happens in that automaton when the event is fired. Events can be classified as local or synchronising. A local events changes the state of only one automaton; a synchronising event changes the states of two or more automata.
Pe={P1, P2, . . . Pk} is a set of event probability functions, one for each event. Each function Pi: G→R describes the probability of occurrence of the event at each global state.
Pt={Pt1, Pt2, . . . Ptkm} is a (possibly empty) set of transition probability functions, one for each pair (event, global state). As described above, when a SAN is in a global state S and an event i is applied, the SAN goes to a state S′, which must be an element of Ei(S). The transition probability functions describe the probabilities of the different elements of Ei(S) being selected. Usually Ei(S) has only one state, in which case these probabilities are not required.
I is a set of initial global states, so is a subset of G. In some definitions, SANs do not have initial states, hence the set I may be empty.
It can be shown that SANs have a number of advantages over Markov chains in modelling complex systems. However, SANs have not yet been applied in testing systems or test case generation.